home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 February: Technology Seed / Mac Tech Seed Feb '97.toast / OpenDoc 1.2b2c1 / Implementation / Memory / BestFitH.h < prev    next >
Encoding:
C/C++ Source or Header  |  1997-02-13  |  22.4 KB  |  795 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        BestFitH.h
  3.  
  4.     Contains:    BestFitHeap class interface
  5.  
  6.     Owned by:    Michael Burbidge
  7.     Owned by:    Jens Alfke
  8.  
  9.     Copyright:    © 1993 - 1996 by Apple Computer, Inc., all rights reserved.
  10.  
  11.     Change History (most recent first):
  12.     
  13.          <3>     9/13/96    jpa        1371387: Deferred-coalesce optimization.
  14.                                     Other speedups. 1371387: Sped up BytesFree.
  15.         <10>      5/4/95    jpa        Support for finding largest free block
  16.                                     [1235657] and validating memory ranges
  17.                                     [1246077]
  18.          <9>     1/25/95    jpa        Removed five-$ comments [1210981]
  19.          <8>    10/24/94    jpa        Constness [1194286]
  20.          <7>     9/29/94    RA        1189812: Mods for 68K build.
  21.          <6>     9/14/94    jpa        Eliminated dependencies on rest of OpenDoc.
  22.                                     Added support for getting the heap of a
  23.                                     block by stuffing heap ptr in busy block
  24.                                     header. [1186692]
  25.          <5>     8/17/94    jpa        (Oops, deleted obsolete "in progress" msg)
  26.          <4>     8/17/94    jpa        Implemented huge-block support [1179565],
  27.                                     segment disposal [1181509] and the
  28.                                     SOM-block flag [1181510].
  29.          <3>      8/8/94    jpa        Added fHugeBlockSize -- not used yet
  30.                                     [1179565]
  31.          <2>     6/10/94    MB        Make it build
  32.          <1>      6/9/94    MB        first checked in
  33.          <4>     5/27/94    MB        #1162181: Fixed MMM integration bug
  34.          <2>      5/9/94    MB        #1162181: Changes necessary to install MMM.
  35.          <1>     4/29/94    MB        first checked in
  36.     To Do:
  37.     In Progress:
  38. */
  39.  
  40. #ifndef _BESTFITH_
  41. #define _BESTFITH_
  42.  
  43. #ifndef _MEMORYHE_
  44. #include "MemoryHe.h"
  45. #endif
  46.  
  47.  
  48. #ifdef MM_DEFER_COALESCE
  49. const int kAvailBlockSizeLimit    = 128;    // Limit of size of 'small' blocks
  50. const int kNAvailListsToCheck    =   4;    // Number of lists to look at when allocating
  51. #endif
  52.  
  53.  
  54. //========================================================================================
  55. // Forward class declarations
  56. //========================================================================================
  57.  
  58. class PrivBestFitBlock;
  59. class BestFitHeap;
  60.  
  61.  
  62. //========================================================================================
  63. // STRUCT PrivBestFitBlockFreeListLinks
  64. //
  65. // The following fields are only present in free blocks. They are used to link the free
  66. // block into the free block tree. The address of a free block is also stored at the end
  67. // of the block and must be accounted for in the minimum block size.
  68. //========================================================================================
  69.  
  70. struct PrivBestFitBlockFreeListLinks
  71. {
  72.     PrivBestFitBlock* fParent;
  73.     PrivBestFitBlock* fLeft;
  74.     PrivBestFitBlock* fRight;
  75. };
  76.  
  77.  
  78. //========================================================================================
  79. // STRUCT PrivBestFitBlockHeader
  80. //========================================================================================
  81.  
  82. // The fBits field of PrivBestFitBlockHeader contains five fields. The following masks are
  83. // used to get and set the fields. The block type field is used to distinguish best fit
  84. // blocks from chunky blocks and must be the first four bits of the last byte in fBits.
  85.  
  86. #ifdef MM_LITTLE_ENDIAN
  87.     // Bytes are in reverse order in a long.
  88.     
  89.     const unsigned long BestFitBlockHeader_kSizeMask = 0x00FFFFFF;
  90.     const unsigned long BestFitBlockHeader_kSizeShift = 0;
  91.     
  92. //    const unsigned long BestFitBlockHeader_kBlockTypeMask = 0xC0000000;
  93. //    const unsigned long BestFitBlockHeader_kBlockTypeShift = 30;
  94.     
  95.     const unsigned long BestFitBlockHeader_kAvailMask = 0x40000000;
  96.     const unsigned long BestFitBlockHeader_kAvailShift = 30;
  97.     
  98.     const unsigned long BestFitBlockHeader_kIsObjectMask = 0x20000000;
  99.     const unsigned long BestFitBlockHeader_kIsObjectShift = 29;
  100.     
  101.     const unsigned long BestFitBlockHeader_kFirstBlockMask = 0x10000000;
  102.     const unsigned long BestFitBlockHeader_kFirstBlockShift = 28;
  103.     
  104.     const unsigned long BestFitBlockHeader_kBusyMask = 0x08000000;
  105.     const unsigned long BestFitBlockHeader_kBusyShift = 27;
  106.     
  107.     const unsigned long BestFitBlockHeader_kPreviousBusyMask = 0x04000000;
  108.     const unsigned long BestFitBlockHeader_kPreviousBusyShift = 26;
  109.     
  110.     const unsigned long BestFitBlockHeader_kMagicNumberMask = 0x03000000;
  111.     const unsigned long BestFitBlockHeader_kMagicNumberShift = 24;
  112. #else
  113.     const unsigned long BestFitBlockHeader_kSizeMask = 0xFFFFFF00;
  114.     const unsigned long BestFitBlockHeader_kSizeShift = 8;
  115.     
  116.     const unsigned long BestFitBlockHeader_kAvailMask = 0x00000040;
  117.     const unsigned long BestFitBlockHeader_kAvailShift = 6;
  118.     
  119. //    const unsigned long BestFitBlockHeader_kBlockTypeMask = 0x000000C0;
  120. //    const unsigned long BestFitBlockHeader_kBlockTypeShift = 6;
  121.     
  122.     const unsigned long BestFitBlockHeader_kIsObjectMask = 0x00000020;
  123.     const unsigned long BestFitBlockHeader_kIsObjectShift = 5;
  124.     
  125.     const unsigned long BestFitBlockHeader_kFirstBlockMask = 0x00000010;
  126.     const unsigned long BestFitBlockHeader_kFirstBlockShift = 4;
  127.     
  128.     const unsigned long BestFitBlockHeader_kBusyMask = 0x00000008;
  129.     const unsigned long BestFitBlockHeader_kBusyShift = 3;
  130.     
  131.     const unsigned long BestFitBlockHeader_kPreviousBusyMask = 0x00000004;
  132.     const unsigned long BestFitBlockHeader_kPreviousBusyShift = 2;
  133.     
  134.     const unsigned long BestFitBlockHeader_kMagicNumberMask = 0x00000003;
  135.     const unsigned long BestFitBlockHeader_kMagicNumberShift = 0;
  136. #endif
  137.  
  138.  
  139.  
  140. class PrivBestFitBlockHeader
  141. {
  142. protected:
  143.     unsigned long fBits;
  144.     union{
  145.         BestFitHeap* fHeap;                    // Busy block
  146.         PrivBestFitBlock* fNext;            // Avail block, or blocklet in free list
  147.         struct {
  148.             PrivBestFitBlock* fParent;        // Free block in tree
  149.             PrivBestFitBlock* fLeft;
  150.             PrivBestFitBlock* fRight;
  151.         } fFreeLinks;
  152.     };
  153. };
  154.  
  155.  
  156. //========================================================================================
  157. // CLASS PrivBestFitBlock
  158. //========================================================================================
  159.  
  160. #ifdef BUILD_WIN16
  161. const ODBlockSize BestFitBlock_kMaxBlockSize = 60L * 1024L;
  162.     // Block size limited by 64K limit of far pointers. Allow 4K for overhead in the
  163.     // various layers.
  164. #else
  165. const ODBlockSize BestFitBlock_kMaxBlockSize = 0x00FFFFFF;
  166. #endif
  167.  
  168.  
  169. class PrivBestFitBlock :PrivBestFitBlockHeader
  170. {
  171. public:
  172.  
  173.     enum
  174.     {
  175.         kBusyOverhead = sizeof(unsigned long) + sizeof(BestFitHeap*),
  176.         kMinBlockSize = sizeof(PrivBestFitBlockHeader) + sizeof(void *), 
  177. //        kBlockTypeId = MemoryHeap::kBlockTypeId + 1, 
  178.         kMagicNumber = 0x3
  179.     };
  180.  
  181.  
  182.     mmboolean operator>(const PrivBestFitBlock& blk) const;
  183.     mmboolean operator<(const PrivBestFitBlock& blk) const;
  184.     mmboolean operator>=(const PrivBestFitBlock& blk) const;
  185.     mmboolean operator<=(const PrivBestFitBlock& blk) const;
  186.     mmboolean operator==(const PrivBestFitBlock& blk) const;
  187.     mmboolean operator!=(const PrivBestFitBlock& blk) const;
  188.  
  189.     inline void operator delete(void *) { };
  190.     void* operator new(SIZE_T, void* ptr);
  191.  
  192.     PrivBestFitBlock(int busy,
  193.                      int prevBusy,
  194.                      long size);
  195.     PrivBestFitBlock(const PrivBestFitBlock& otherBlock);
  196.  
  197.     BestFitHeap*        GetHeap() const;
  198.     mmboolean        GetBusy() const;
  199.     mmboolean        GetAvail() const;
  200.     mmboolean        GetIsFirst() const;
  201.     mmboolean        GetIsObject() const;
  202.     PrivBestFitBlock*    GetLeft() const;
  203.     unsigned int        GetMagicNumber() const;
  204.     PrivBestFitBlock*    GetNext() const;
  205.     PrivBestFitBlock*    GetParent() const;
  206.     mmboolean        GetPrevBusy() const;
  207.     PrivBestFitBlock*    GetRight() const;
  208.     ODBlockSize            GetSize() const;
  209. //    unsigned short        GetBlockType() const;
  210.  
  211.     void SetHeap(BestFitHeap*);    
  212.     void SetBusy(mmboolean busy);
  213.     void SetAvail(mmboolean busy);
  214.     void SetIsFirst(mmboolean first);
  215.     void SetIsObject(mmboolean isObj);
  216.     void SetLeft(PrivBestFitBlock* left);
  217.     void SetNext(PrivBestFitBlock* next);
  218.     void SetParent(PrivBestFitBlock* parent);
  219.     void SetPrevBusy(mmboolean busy);
  220.     void SetRight(PrivBestFitBlock* right);
  221.     void SetSize(ODBlockSize size);
  222. //    void SetBlockType(unsigned long blockType);
  223.     void SetMagicNumber(unsigned long magicNumber);
  224.  
  225.     void StuffAddressAtEnd();
  226.     PrivBestFitBlock* GetPrevBlock();
  227.     PrivBestFitBlock* GetNextBlock();
  228.  
  229. //    PrivBestFitBlock* Coalesce( );
  230.  
  231. private:
  232.     PrivBestFitBlock& operator=(const PrivBestFitBlock& blk);//illegal
  233.     void* operator new(SIZE_T);
  234. };
  235.  
  236. inline void* PrivBestFitBlock::operator new(SIZE_T, void* ptr)
  237. {
  238.     return ptr;
  239. }
  240.  
  241. /*inline PrivBestFitBlock& PrivBestFitBlock::operator=(const PrivBestFitBlock& blk)
  242. {
  243.     fHeader = blk.fHeader;
  244.     return (*this);
  245. }*/
  246.  
  247. /*inline PrivBestFitBlock::PrivBestFitBlock(const PrivBestFitBlock& blk) :
  248.     fHeader(blk.fHeader)
  249. {
  250. }*/
  251.  
  252. inline mmboolean PrivBestFitBlock::GetBusy() const
  253. {
  254.     return (fBits & BestFitBlockHeader_kBusyMask) != 0;
  255. }
  256.  
  257. inline mmboolean PrivBestFitBlock::GetAvail() const
  258. {
  259.     return (fBits & BestFitBlockHeader_kAvailMask) != 0;
  260. }
  261.  
  262. inline mmboolean PrivBestFitBlock::GetIsFirst() const
  263. {
  264.     return (fBits & BestFitBlockHeader_kFirstBlockMask) != 0;
  265. }
  266.  
  267. inline mmboolean PrivBestFitBlock::GetIsObject() const
  268. {
  269.     return (fBits & BestFitBlockHeader_kIsObjectMask) != 0;
  270. }
  271.  
  272. inline PrivBestFitBlock* PrivBestFitBlock::GetLeft() const
  273. {
  274.     return fFreeLinks.fLeft;
  275. }
  276.  
  277. inline unsigned int PrivBestFitBlock::GetMagicNumber() const
  278. {
  279.     return (fBits & BestFitBlockHeader_kMagicNumberMask)
  280.                 >> BestFitBlockHeader_kMagicNumberShift;
  281. }
  282.  
  283. inline PrivBestFitBlock* PrivBestFitBlock::GetNext() const
  284. {
  285.     MM_ASSERT(!this->GetBusy() || this->GetAvail());
  286.     return fNext;
  287. }
  288.  
  289. inline PrivBestFitBlock* PrivBestFitBlock::GetParent() const
  290. {
  291.     return fFreeLinks.fParent;
  292. }
  293.  
  294. inline mmboolean PrivBestFitBlock::GetPrevBusy() const
  295. {
  296.     return (fBits & BestFitBlockHeader_kPreviousBusyMask) != 0;
  297. }
  298.  
  299. inline PrivBestFitBlock* PrivBestFitBlock::GetRight() const
  300. {
  301.     return fFreeLinks.fRight;
  302. }
  303.  
  304. inline ODBlockSize PrivBestFitBlock::GetSize() const
  305. {
  306. #ifdef MM_LITTLE_ENDIAN
  307.     return (fBits & BestFitBlockHeader_kSizeMask)
  308.                 >> BestFitBlockHeader_kSizeShift;
  309. #else
  310.     return fBits >> BestFitBlockHeader_kSizeShift;
  311. #endif
  312. }
  313.  
  314. /*inline unsigned short PrivBestFitBlock::GetBlockType() const
  315. {
  316.     return (fBits & BestFitBlockHeader_kBlockTypeMask)
  317.                 >> BestFitBlockHeader_kBlockTypeShift;
  318. }*/
  319.  
  320. inline void PrivBestFitBlock::SetBusy(mmboolean busy)
  321. {
  322.     if (busy)
  323.         fBits |=  BestFitBlockHeader_kBusyMask;
  324.     else
  325.         fBits &= ~BestFitBlockHeader_kBusyMask;
  326. }
  327.  
  328. inline void PrivBestFitBlock::SetAvail(mmboolean avail)
  329. {
  330.     if (avail)
  331.         fBits |=  BestFitBlockHeader_kAvailMask;
  332.     else
  333.         fBits &= ~BestFitBlockHeader_kAvailMask;
  334. }
  335.  
  336. inline void PrivBestFitBlock::SetIsFirst(mmboolean first)
  337. {
  338.     if (first)
  339.         fBits |=  BestFitBlockHeader_kFirstBlockMask;
  340.     else
  341.         fBits &= ~BestFitBlockHeader_kFirstBlockMask;
  342. }
  343.  
  344. inline void PrivBestFitBlock::SetIsObject(mmboolean isObj)
  345. {
  346.     if (isObj)
  347.         fBits |=  BestFitBlockHeader_kIsObjectMask;
  348.     else
  349.         fBits &= ~BestFitBlockHeader_kIsObjectMask;
  350. }
  351.  
  352. inline void PrivBestFitBlock::SetLeft(PrivBestFitBlock* left)
  353. {
  354.     fFreeLinks.fLeft = left;
  355. }
  356.  
  357. inline void PrivBestFitBlock::SetNext(PrivBestFitBlock* next)
  358. {
  359.     MM_ASSERT(!this->GetBusy() || this->GetAvail());
  360.     fNext = next;
  361. }
  362.  
  363. inline void PrivBestFitBlock::SetParent(PrivBestFitBlock* parent)
  364. {
  365.     fFreeLinks.fParent = parent;
  366. }
  367.  
  368. inline void PrivBestFitBlock::SetPrevBusy(mmboolean busy)
  369. {
  370.     if (busy)
  371.         fBits |= BestFitBlockHeader_kPreviousBusyMask;
  372.     else
  373.         fBits &= ~BestFitBlockHeader_kPreviousBusyMask;
  374. }
  375.  
  376. inline void PrivBestFitBlock::SetRight(PrivBestFitBlock* right)
  377. {
  378.     fFreeLinks.fRight = right;
  379. }
  380.  
  381. inline void PrivBestFitBlock::SetSize(ODBlockSize size)
  382. {
  383. #ifdef MM_LITTLE_ENDIAN
  384.     fBits &= ~BestFitBlockHeader_kSizeMask;
  385.     fBits |= (size << BestFitBlockHeader_kSizeShift)
  386.                         & BestFitBlockHeader_kSizeMask;
  387. #else
  388.     fBits = (fBits & ~BestFitBlockHeader_kSizeMask) | (size<<BestFitBlockHeader_kSizeShift);
  389. #endif
  390. }
  391.  
  392. /*inline void PrivBestFitBlock::SetBlockType(unsigned long blockType)
  393. {
  394.     fBits &= ~BestFitBlockHeader_kBlockTypeMask;
  395.     fBits |= (blockType << BestFitBlockHeader_kBlockTypeShift)
  396.                         & BestFitBlockHeader_kBlockTypeMask;
  397. }*/
  398.  
  399. inline void PrivBestFitBlock::SetMagicNumber(unsigned long magicNumber)
  400. {
  401.     fBits &= ~BestFitBlockHeader_kMagicNumberMask;
  402.     fBits |= (magicNumber << BestFitBlockHeader_kMagicNumberShift)
  403.                         & BestFitBlockHeader_kMagicNumberMask;
  404. }
  405.  
  406. inline BestFitHeap* PrivBestFitBlock::GetHeap() const
  407. {
  408.     MM_ASSERT(this->GetBusy() && !this->GetAvail());
  409.     return fHeap;
  410. }
  411.  
  412. inline void PrivBestFitBlock::SetHeap(BestFitHeap *heap)
  413. {
  414.     MM_ASSERT(this->GetBusy() && !this->GetAvail());
  415.     fHeap = heap;
  416. }
  417.  
  418. inline mmboolean PrivBestFitBlock::operator>(const PrivBestFitBlock& blk) const
  419. {
  420.     if (GetSize() == blk.GetSize())
  421.         return this > &blk;
  422.     else
  423.         return GetSize() > blk.GetSize();
  424. }
  425.  
  426. inline mmboolean PrivBestFitBlock::operator<(const PrivBestFitBlock& blk) const
  427. {
  428.     if (GetSize() == blk.GetSize())
  429.         return this < &blk;
  430.     else
  431.         return GetSize() < blk.GetSize();
  432. }
  433.  
  434. inline mmboolean PrivBestFitBlock::operator==(const PrivBestFitBlock& blk) const
  435. {
  436.     return /*GetSize() == blk.GetSize() &&*/ this == &blk;
  437. }
  438.  
  439. inline mmboolean PrivBestFitBlock::operator>=(const PrivBestFitBlock& blk) const
  440. {
  441.     return *this > blk || *this == blk;
  442. }
  443.  
  444. inline mmboolean PrivBestFitBlock::operator<=(const PrivBestFitBlock& blk) const
  445. {
  446.     return *this < blk || *this == blk;
  447. }
  448.  
  449. inline mmboolean PrivBestFitBlock::operator!=(const PrivBestFitBlock& blk) const
  450. {
  451.     return !(*this == blk);
  452. }
  453.  
  454. inline void PrivBestFitBlock::StuffAddressAtEnd()
  455. {
  456.     // coalescence possible in constant time.
  457.  
  458.     if (!this->GetBusy())
  459.     {
  460.         void** addr= (void**) ((ODBytePtr) this + this->GetSize() - sizeof(PrivBestFitBlock *));
  461.         *addr = this;
  462.     }
  463. #if MM_DEBUG
  464.     else
  465.         MM_WARN("PrivBestFitBlock::StuffAddressAtEnd: corrupt heap!");
  466. #endif
  467. }
  468.  
  469. inline PrivBestFitBlock* PrivBestFitBlock::GetPrevBlock( )
  470. {
  471.     MM_ASSERT(!this->GetPrevBusy());
  472.     return *(PrivBestFitBlock **) ((ODBytePtr) this - sizeof(ODBlockSize));
  473. }
  474.  
  475. inline PrivBestFitBlock* PrivBestFitBlock::GetNextBlock( )
  476. {
  477.     return (PrivBestFitBlock*) ((ODBytePtr) this + this->GetSize());
  478. }
  479.  
  480.  
  481. //----------------------------------------------------------------------------------------
  482. // PrivBestFitBlock::PrivBestFitBlock
  483. //----------------------------------------------------------------------------------------
  484.  
  485. inline PrivBestFitBlock::PrivBestFitBlock(int busy,
  486.                                           int previousBusy,
  487.                                           long size)
  488. {
  489.     fBits = ((size << BestFitBlockHeader_kSizeShift) & BestFitBlockHeader_kSizeMask)
  490.           | (kMagicNumber << BestFitBlockHeader_kMagicNumberShift);
  491.     
  492. // Directly initializing fBits (above) has the effect of all of the following:
  493. //    SetSize(size);
  494. //    SetIsFirst(false);
  495. //    SetIsObject(false);
  496. //    SetBlockType(kBlockTypeId);
  497. //    SetMagicNumber(kMagicNumber);
  498. //    SetAvail(false);
  499.  
  500.     if( previousBusy )
  501.         SetPrevBusy(true);
  502.  
  503.     if (busy)
  504.         SetBusy(true);
  505.     else {
  506.         SetParent(NULL);
  507.         SetRight(NULL);
  508.         SetLeft(NULL);
  509.         this->StuffAddressAtEnd();
  510.     }
  511. }
  512.  
  513.  
  514. //========================================================================================
  515. // CLASS PrivBestFitSegment
  516. //
  517. //        The BestFitHeap allocates memory from the system in segments. The segments are
  518. //        linked together in a list so that when the heap is destroyed all segments can be
  519. //        freed.
  520. //
  521. //========================================================================================
  522.  
  523. class PrivBestFitSegment
  524. {
  525. public:
  526.  
  527.     friend BestFitHeap;
  528.  
  529.     enum
  530.     {
  531.         kSegmentPrefixSize = 12,
  532.         kSegmentSuffixSize = 4,
  533.         kSegmentOverhead = kSegmentPrefixSize + kSegmentSuffixSize
  534.     };
  535.  
  536.     mmboolean AddressInSegment(const void* ptr);
  537.     mmboolean CheckSegment( HeapWalkProc, void *refCon,
  538.                           ODBlockSize blockHeaderSize, ODBlockSize sizeDelta );
  539.     mmboolean    Coalesce( BestFitHeap*, mmboolean &coalescence );
  540.  
  541. #if MM_DEBUG
  542.     mmboolean FindBlockContaining( const void *start, const void *end,
  543.                         const void* &blockStart, const void* &blockEnd ) const;
  544. #endif
  545.  
  546. private:
  547.     void *fSegmentSpace;
  548.     unsigned long fSegmentSize;
  549.     PrivBestFitSegment *fNextSegment;
  550.     
  551.     PrivBestFitSegment(const PrivBestFitSegment& blk);
  552.     PrivBestFitSegment& operator=(const PrivBestFitSegment& blk);
  553.         // This class shouldn't be copied.
  554. };
  555.  
  556. //----------------------------------------------------------------------------------------
  557. // INLINES PrivBestFitSegment
  558. //----------------------------------------------------------------------------------------
  559.  
  560. inline mmboolean PrivBestFitSegment::AddressInSegment(const void* ptr)
  561. {
  562.     return ptr >= fSegmentSpace &&
  563.             ptr <= (void*) ((ODBytePtr) fSegmentSpace + fSegmentSize);
  564. }
  565.  
  566.  
  567. //========================================================================================
  568. // CLASS PrivFreeBlockTree
  569. //
  570. //        Binary tree for storing free blocks. Dependent on the structure and
  571. //        implementation of PrivBestFitBlock.
  572. //
  573. //========================================================================================
  574.  
  575. class PrivFreeBlockTree
  576. {
  577. public:
  578.     PrivFreeBlockTree();
  579.     PrivFreeBlockTree(const PrivFreeBlockTree& blk);
  580.  
  581.     PrivFreeBlockTree& operator=(const PrivFreeBlockTree& blk);
  582.  
  583.     void AddBlock(PrivBestFitBlock* blk);
  584.     void TreeInfo(unsigned long& bytesFree,
  585.                   unsigned long& numberOfNodes) const;
  586.     void RemoveBlock(PrivBestFitBlock* blk);
  587.     PrivBestFitBlock* SearchForBlock(ODBlockSize size,
  588.                                      void* blk,
  589.                                      PrivBestFitBlock** insertLeaf = NULL);
  590.     const PrivBestFitBlock* FindLargestBlock( ) const;
  591.  
  592. #if MM_DEBUG
  593.     void CheckTree() const;
  594.     void PrintTree() const;
  595. #endif
  596.  
  597. protected:
  598.     PrivBestFitBlock* GetSuccessorBlk(PrivBestFitBlock* blk);
  599.     void TreeInfoHelper(PrivBestFitBlock* blk,
  600.                         unsigned long& bytesFree,
  601.                         unsigned long& numberOfNodes) const;
  602.  
  603. #if MM_DEBUG
  604.     void CheckTreeHelper(PrivBestFitBlock* blk) const;
  605.     void PrintTreeHelper(PrivBestFitBlock* blk,
  606.                          int level = 0) const;
  607. #endif
  608.  
  609. private:
  610.     PrivBestFitBlock fRoot;
  611.  
  612. };
  613.  
  614.  
  615. //========================================================================================
  616. // CLASS PrivFreeBlockList
  617. //
  618. //        Linked list of free blocks. Used for small blocks that can't hold tree nodes.
  619. //
  620. //========================================================================================
  621.  
  622. class PrivFreeBlockList
  623. {
  624. public:
  625.                         PrivFreeBlockList( )        {fFirst=NULL;}
  626.     
  627.     long                NotEmpty( )                    {return fFirst!=NULL;}
  628.     PrivBestFitBlock*    First( )                    {return fFirst;}
  629.     void                ForceEmpty( )                {fFirst = NULL;}
  630.     void                ForceFirst( PrivBestFitBlock *f ) {fFirst = f;}
  631.     
  632.     PrivBestFitBlock*    GetBlock( );                // do not call on empty list
  633.     void                AddBlock( PrivBestFitBlock *b );
  634.  
  635. private:
  636.     PrivBestFitBlock *fFirst;    // First block, or NULL if list is empty
  637.     PrivBestFitBlock *fLast;    // Last block. Invalid if list is empty.
  638. };
  639.  
  640. inline PrivBestFitBlock*
  641. PrivFreeBlockList::GetBlock( )
  642. {
  643.     PrivBestFitBlock *b = fFirst;
  644.     fFirst = fFirst->GetNext();
  645.     return b;
  646. }
  647.  
  648. inline void
  649. PrivFreeBlockList::AddBlock( PrivBestFitBlock *b )
  650. {
  651.     b->SetNext(NULL);
  652.     if( fFirst )
  653.         fLast->SetNext(b);
  654.     else
  655.         fFirst = b;
  656.     fLast = b;
  657. }
  658.  
  659.  
  660. //========================================================================================
  661. // CLASS BestFitHeap
  662. //
  663. //        Memory allocation heap using the best fit allocation strategy.
  664. //
  665. //========================================================================================
  666.  
  667. class BestFitHeap : public MemoryHeap
  668. {
  669. public:
  670.  
  671.     virtual unsigned long BytesFree() const        {return fFreeBytes+fAvailBytes;}
  672.     virtual unsigned long HeapSize() const;
  673.  
  674.     BestFitHeap(unsigned long sizeInitial,
  675.                   unsigned long sizeIncrement = 0,
  676.                   unsigned long hugeBlockSize = 0,        // "0" means sizeIncrement/2
  677.                   MMHeapLocation = kMMTempMemory);
  678.     virtual ~BestFitHeap();
  679.  
  680.     void IBestFitHeap();
  681.     void ExpandHeap(unsigned long sizeInitial, unsigned long sizeIncrement);
  682.     
  683.     long GetSizeIncrement( )    {return fSizeIncrement;}
  684.     long GetHugeBlockSize( )    {return fSizeIncrement;}
  685.     
  686. #ifdef MM_DEFER_COALESCE
  687.     void Coalesce()            {this->Coalesce(BestFitBlock_kMaxBlockSize);}
  688.     PrivBestFitBlock* Coalesce( ODBlockSize sizeNeeded );
  689. #endif
  690.  
  691. #if MM_DEBUG
  692.     virtual void Check( HeapWalkProc proc =NULL, void *refCon =NULL ) const;
  693.     virtual mmboolean IsMyBlock(const void* blk) const;
  694.     virtual void Print(char* msg = "") const;
  695. #endif
  696.  
  697. protected:
  698.  
  699.     void AddToFreeBlocks(PrivBestFitBlock* blk);
  700.     PrivBestFitBlock* BasicFreeBlock( PrivBestFitBlock* );
  701.     PrivBestFitBlock* CreateNewSegment(unsigned long size);        //returns free block --jpa
  702.     mmboolean DeleteSegmentIfEmpty( PrivBestFitBlock *blk );
  703.     void DeleteSegment( PrivBestFitSegment *seg );
  704.     void DeleteSegments();
  705.     void GrowHeap(unsigned long sizeIncrement);
  706.     void RemoveFromFreeBlocks(PrivBestFitBlock* blk);
  707.     PrivBestFitBlock* SearchFreeBlocks(ODBlockSize size);
  708.  
  709.     virtual void* DoAllocate(ODBlockSize size, ODBlockSize& allocatedSize);
  710.     virtual ODBlockSize DoBlockSize(const void* block) const;
  711.     virtual void DoFree(void*);
  712. //    virtual void DoReset();
  713.     virtual unsigned long DoLargestFreeBlock() const;
  714.  
  715.     virtual void DoSetBlockIsObject( void* ptr, mmboolean isObject );
  716.     
  717.     virtual mmboolean DoBlockIsObject( const void* ptr ) const;
  718.  
  719.     virtual MemoryHeap* DoGetBlockHeap( const void* ) const;
  720.  
  721. #if MM_DEBUG
  722.     virtual void CompilerCheck();
  723.     virtual mmboolean DoIsValidBlock(const void* blk) const;
  724.     mmboolean DoFindBlockContaining( const void *start, const void *end,
  725.                         const void* &blockStart, const void* &blockEnd ) const;
  726. #endif
  727.  
  728. private:
  729.     void AddFreeBytes( long n )
  730. #if MM_DEBUG_COALESCE
  731.                                 ;
  732. #else
  733.                                 {fFreeBytes += n;}
  734. #endif
  735.  
  736.     PrivBestFitSegment* fSegments;
  737.     unsigned long fSizeIncrement;
  738.     unsigned long fSizeInitial;
  739.     unsigned long fHugeBlockSize;
  740.     ODBlockSize fFreeBytes;
  741.     ODBlockSize fAvailBytes;            // Size of blocks in avail lists
  742.     PrivFreeBlockTree fFreeTree;
  743.     
  744. #ifdef MM_DEFER_COALESCE
  745.     enum{
  746.         // We need a list for every multiple of 4 bytes over the minimum size.
  747.         // The block-size limit needs to be translated into physical sizes (+overhead).
  748.         // And leave extra blocks at end so we don't fall off the end while searching.
  749.         kNAvailBlockLists = ((kAvailBlockSizeLimit+PrivBestFitBlock::kBusyOverhead
  750.                                                   -PrivBestFitBlock::kMinBlockSize) >>2)
  751.     };
  752.     PrivFreeBlockList      fAvailBlocks[kNAvailBlockLists + kNAvailListsToCheck-1];
  753. #endif
  754.  
  755.     enum{ kMaxHugeBlockSize = 65535L };
  756.     
  757.     BestFitHeap(const BestFitHeap& blk);
  758.     BestFitHeap& operator=(const BestFitHeap& blk);
  759.         // This class shouldn't be copied.
  760.     
  761.     friend mmboolean PrivBestFitSegment::Coalesce( BestFitHeap*,mmboolean& );
  762. };
  763.  
  764.  
  765. //----------------------------------------------------------------------------------------
  766. // BestFitHeap::AddToFreeBlocks
  767. //----------------------------------------------------------------------------------------
  768.  
  769. inline void BestFitHeap::AddToFreeBlocks(PrivBestFitBlock* blk)
  770. {
  771.     fFreeTree.AddBlock(blk);
  772.     this->AddFreeBytes(blk->GetSize());
  773. }
  774.  
  775. //----------------------------------------------------------------------------------------
  776. // BestFitHeap::RemoveFromFreeBlocks
  777. //----------------------------------------------------------------------------------------
  778.  
  779. inline void BestFitHeap::RemoveFromFreeBlocks(PrivBestFitBlock* blk)
  780. {
  781.     fFreeTree.RemoveBlock(blk);
  782.     this->AddFreeBytes(-blk->GetSize());
  783. }
  784.  
  785. //----------------------------------------------------------------------------------------
  786. // BestFitHeap::SearchFreeBlocks
  787. //----------------------------------------------------------------------------------------
  788.  
  789. inline PrivBestFitBlock* BestFitHeap::SearchFreeBlocks(ODBlockSize size)
  790. {
  791.     return fFreeTree.SearchForBlock(size, NULL, NULL);
  792. }
  793.  
  794. #endif
  795.